package leetcode_700;

import java.util.Arrays;

public class PartitionToKEqualSumSubsets_698 {
	
	
	/**
	 * describe:递归回溯法解决 AC 83% 很大原因是因为数组太短了
	 * 2018年10月10日 上午10:34:51
	 */
	public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum=0;
        for(int i:nums)
        	sum+=i;
        if(sum%k!=0)
        	return false;
        sum/=k;
        boolean visited[]=new boolean[nums.length];
        return help(nums,visited,0,k,0,sum);
        
    }
	
	public boolean help(int []nums,boolean []visited,int index,int remain,int sum,int target) {
		if(remain==1)
			return true;
		if(sum>target)
			return false;
		if(sum==target) {
			return help(nums,visited,0,remain-1,0,target);//那么从头开始搜索下一个可能
		}
		for(int i=index;i<nums.length;++i) {
			if(!visited[i]) {
				visited[i]=true;
				if(help(nums,visited,i,remain,sum+nums[i],target))
					return true;
				visited[i]=false;//回溯
			}
		}
		return false;
	}
	
	
	/**
	 * describe:这样每次选择最大和最小组合的贪心算法是错误的 
	 * see:[4,15,1,1,1,1,3,11,1,10] 3 把1用完了就结束了
	 * 2018年10月10日 上午9:54:39
	 */
	public boolean canPartitionKSubsets1(int[] nums, int k) {
        int sum=0;
        for(int i:nums)
        	sum+=i;
        if(sum%k!=0)
        	return false;
        sum/=k;
        Arrays.sort(nums);
        int left=0,right=nums.length-1;
        while(left<right) {
        	if(nums[right]==sum)
        		--right;
        	else if(nums[right]<sum) {
        		nums[right]+=nums[left];
        		++left;
        	}
        	else
        		return false;
        }
        return true;
    }
}
